package com.java.Collection.List.LinkedList.source_analyze.source_code;

import java.util.Collection;

public class LinkedList<E> {
    // modCount指集合变化的次数，与迭代器并发修改异常相关
    
    // 集合长度 or 节点个数
    transient int size = 0;
    
    // 头节点
    transient Node<E> first;
    
    // 尾节点
    transient Node<E> last;
    
    // 双向链表节点类
    private static class Node<E> {
        E item; // 当前节点数据
        Node<E> next; // 下个节点
        Node<E> prev; // 上个节点
        
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    
    public LinkedList() {
    }
    
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    void linkLast(E e) {
        final Node<E> l = last;
        
        // 为新添加的元素创建节点
        final Node<E> newNode = new Node<>(l, e, null);
        
        // 更新尾节点
        last = newNode;
        
        // 若原链表为空则设置头节点，否则更新原尾节点的下一个节点为新节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        
        // 更新节点数量
        size++;
        // modCount++;
    }
    
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    
    public boolean addAll(int index, Collection<? extends E> c) {
        // 判断索引index在链表中是否有效，无效则抛出异常并终止程序
        checkPositionIndex(index);
        
        Object[] a = c.toArray();
        int numNew = a.length;
        
        // 集合内无元素则添加失败
        if (numNew == 0)
            return false;
        
        Node<E> pred, succ; // pred和succ分别表示添加位置的上个节点和添加位置的当前节点
        if (index == size) { // 添加尾节点
            succ = null; // 添加位置的当前节点为空
            pred = last; // 添加位置的上个节点为尾节点
        } else { // 添加非尾节点，在链表中间添加
            // node寻找添加位置的当前节点
            succ = node(index);
            pred = succ.prev;
        }
        
        // 循环添加集合内每个元素
        for (Object o : a) {
            // @SuppressWarnings抑制强转异常
            @SuppressWarnings("unchecked") E e = (E) o;
            
            // 为新添加的元素创建节点
            Node<E> newNode = new Node<>(pred, e, null);
            
            // 若添加位置的上个节点为空则设置头节点，否则更新添加位置的上个节点的下一个节点为新节点
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            
            // 更新添加位置的上个节点
            pred = newNode;
        }
        
        // 若添加位置的当前节点为空则设置尾节点，否则更新最后添加位置的上个节点的下一个节点为添加位置的当前节点，同事更新添加位置的当前节点的上一个节点为最后添加位置的上个节点
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        
        // 更新节点数量
        size += numNew;
        // modCount++;
        return true;
    }
    
    private void checkPositionIndex(int index) {
        // 判断索引index在链表中是否有效，无效则抛出异常并终止程序
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        
    }
    
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    
    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }
    
    Node<E> node(int index) {
        // 索引在链表前半段则从前往后找，索引在链表后半段则从后往前找，提示查找效率
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    
    public E get(int index) {
        // 判断索引index在链表中是否有效，无效则抛出异常并终止程序
        checkElementIndex(index);
        
        // node寻找添加位置的当前节点
        return node(index).item;
    }
    
    private void checkElementIndex(int index) {
        // 判断索引index在链表中是否有效，无效则抛出异常并终止程序
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }
    
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
    
    public int size() {
        return size;
    }
}
